// Copyright 2016 The Draco Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
#ifndef DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_
#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_

#include <unordered_map>
#include <unordered_set>

#include "draco/draco_features.h"

#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h"
#include "draco/compression/attributes/mesh_traversal_sequencer.h"
#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h"
#include "draco/compression/mesh/mesh_edgebreaker_shared.h"
#include "draco/core/decoder_buffer.h"
#include "draco/mesh/corner_table.h"
#include "draco/mesh/mesh_attribute_corner_table.h"

namespace draco {

// Implementation of the edgebreaker decoder that decodes data encoded with the
// MeshEdgeBreakerEncoderImpl class. The implementation of the decoder is based
// on the algorithm presented in Isenburg et al'02 "Spirale Reversi: Reverse
// decoding of the Edgebreaker encoding". Note that the encoding is still based
// on the standard edgebreaker method as presented in "3D Compression
// Made Simple: Edgebreaker on a Corner-Table" by Rossignac at al.'01.
// http://www.cc.gatech.edu/~jarek/papers/CornerTableSMI.pdf. One difference is
// caused by the properties of the spirale reversi algorithm that decodes the
// symbols from the last one to the first one. To make the decoding more
// efficient, we encode all symbols in the reverse order, therefore the decoder
// can process them one by one.
// The main advantage of the spirale reversi method is that the partially
// decoded mesh has valid connectivity data at any time during the decoding
// process (valid with respect to the decoded portion of the mesh). The standard
// Edgebreaker decoder used two passes (forward decoding + zipping) which not
// only prevented us from having a valid connectivity but it was also slower.
// The main benefit of having the valid connectivity is that we can use the
// known connectivity to predict encoded symbols that can improve the
// compression rate.
template <class TraversalDecoderT>
class MeshEdgeBreakerDecoderImpl : public MeshEdgeBreakerDecoderImplInterface {
  public:
    MeshEdgeBreakerDecoderImpl();
    bool Init(MeshEdgeBreakerDecoder *decoder) override;

    const MeshAttributeCornerTable *GetAttributeCornerTable(
        int att_id) const override;
    const MeshAttributeIndicesEncodingData *GetAttributeEncodingData(
        int att_id) const override;

    bool CreateAttributesDecoder(int32_t att_decoder_id) override;
    bool DecodeConnectivity() override;
    bool OnAttributesDecoded() override;
    MeshEdgeBreakerDecoder *GetDecoder() const override {
        return decoder_;
    }
    const CornerTable *GetCornerTable() const override {
        return corner_table_.get();
    }

  private:
    // Creates a vertex traversal sequencer for the specified |TraverserT| type.
    template <class TraverserT>
    std::unique_ptr<PointsSequencer> CreateVertexTraversalSequencer(
        MeshAttributeIndicesEncodingData *encoding_data);

    // Decodes connectivity between vertices (vertex indices).
    // Returns the number of vertices created by the decoder or -1 on error.
    int DecodeConnectivity(int num_symbols);

    // Returns true if the current symbol was part of a topology split event. This
    // means that the current face was connected to the left edge of a face
    // encoded with the TOPOLOGY_S symbol. |out_symbol_edge| can be used to
    // identify which edge of the source symbol was connected to the TOPOLOGY_S
    // symbol.
    bool IsTopologySplit(int encoder_symbol_id, EdgeFaceName *out_face_edge,
                         int *out_encoder_split_symbol_id) {
        if (topology_split_data_.size() == 0)
            return false;
        if (topology_split_data_.back().source_symbol_id > encoder_symbol_id) {
            // Something is wrong; if the desired source symbol is greater than the
            // current encoder_symbol_id, we missed it, or the input was tampered
            // (|encoder_symbol_id| keeps decreasing).
            // Return invalid symbol id to notify the decoder that there was an
            // error.
            *out_encoder_split_symbol_id = -1;
            return true;
        }
        if (topology_split_data_.back().source_symbol_id != encoder_symbol_id)
            return false;
        *out_face_edge =
            static_cast<EdgeFaceName>(topology_split_data_.back().source_edge);
        *out_encoder_split_symbol_id = topology_split_data_.back().split_symbol_id;
        // Remove the latest split event.
        topology_split_data_.pop_back();
        return true;
    }

    // Decodes event data for hole and topology split events and stores them for
    // future use.
    // Returns the number of parsed bytes, or -1 on error.
    int32_t DecodeHoleAndTopologySplitEvents(DecoderBuffer *decoder_buffer);

    // Decodes all non-position attribute connectivity on the currently
    // processed face.
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
    bool DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner);
#endif
    bool DecodeAttributeConnectivitiesOnFace(CornerIndex corner);

    // Initializes mapping between corners and point ids.
    bool AssignPointsToCorners(int num_connectivity_verts);

    bool IsFaceVisited(CornerIndex corner_id) const {
        if (corner_id < 0)
            return true;  // Invalid corner signalizes that the face does not exist.
        return visited_faces_[corner_table_->Face(corner_id).value()];
    }

    void SetOppositeCorners(CornerIndex corner_0, CornerIndex corner_1) {
        corner_table_->SetOppositeCorner(corner_0, corner_1);
        corner_table_->SetOppositeCorner(corner_1, corner_0);
    }

    MeshEdgeBreakerDecoder *decoder_;

    std::unique_ptr<CornerTable> corner_table_;

    // Stack used for storing corners that need to be traversed when decoding
    // mesh vertices. New corner is added for each initial face and a split
    // symbol, and one corner is removed when the end symbol is reached.
    // Stored as member variable to prevent frequent memory reallocations when
    // handling meshes with lots of disjoint components.  Originally, we used
    // recursive functions to handle this behavior, but that can cause stack
    // memory overflow when compressing huge meshes.
    std::vector<CornerIndex> corner_traversal_stack_;

    // Array stores the number of visited visited for each mesh traversal.
    std::vector<int> vertex_traversal_length_;

    // List of decoded topology split events.
    std::vector<TopologySplitEventData> topology_split_data_;

    // List of decoded hole events.
    std::vector<HoleEventData> hole_event_data_;

    // Configuration of the initial face for each mesh component.
    std::vector<bool> init_face_configurations_;

    // Initial corner for each traversal.
    std::vector<CornerIndex> init_corners_;

    // Id of the last processed input symbol.
    int last_symbol_id_;

    // Id of the last decoded vertex.
    int last_vert_id_;

    // Id of the last decoded face.
    int last_face_id_;

    // Array for marking visited faces.
    std::vector<bool> visited_faces_;
    // Array for marking visited vertices.
    std::vector<bool> visited_verts_;
    // Array for marking vertices on open boundaries.
    std::vector<bool> is_vert_hole_;

    // The number of new vertices added by the encoder (because of non-manifold
    // vertices on the input mesh).
    // If there are no non-manifold edges/vertices on the input mesh, this should
    // be 0.
    int num_new_vertices_;
    // For every newly added vertex, this array stores it's mapping to the
    // parent vertex id of the encoded mesh.
    std::unordered_map<int, int> new_to_parent_vertex_map_;
    // The number of vertices that were encoded (can be different from the number
    // of vertices of the input mesh).
    int num_encoded_vertices_;

    // Array for storing the encoded corner ids in the order their associated
    // vertices were decoded.
    std::vector<int32_t> processed_corner_ids_;

    // Array storing corners in the order they were visited during the
    // connectivity decoding (always storing the tip corner of each newly visited
    // face).
    std::vector<int> processed_connectivity_corners_;

    MeshAttributeIndicesEncodingData pos_encoding_data_;

    // Data for non-position attributes used by the decoder.
    struct AttributeData {
        AttributeData() : decoder_id(-1), is_connectivity_used(true) {}
        // Id of the attribute decoder that was used to decode this attribute data.
        int decoder_id;
        MeshAttributeCornerTable connectivity_data;
        // Flag that can mark the connectivity_data invalid. In such case the base
        // corner table of the mesh should be used instead.
        bool is_connectivity_used;
        MeshAttributeIndicesEncodingData encoding_data;
        // Opposite corners to attribute seam edges.
        std::vector<int32_t> attribute_seam_corners;
    };
    std::vector<AttributeData> attribute_data_;

    TraversalDecoderT traversal_decoder_;
};

}  // namespace draco

#endif  // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_
